package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeParentNode;

/***
 * @description: 寻找后继节点
 *      后继节点：中序遍历中，这个节点（X）的下一个节点
 *      从结构下手，找 X 的后继节点
 *      1）X 有右子树，那么它右子树的最左节点就是它的后继节点
 *      2）X 无右树，一路往上找，当经过的某个节点是其父节点的左孩子的时候，该节点的父节点就是 X 的后继节点
 * @author : 青石路
 * @date: 2021/12/11 11:27
 */
public class SuccessorNode {


    public static TreeParentNode<String> getSuccessorNode(TreeParentNode<String> node) {
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            TreeParentNode parent = node.parent;
            if (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static TreeParentNode getLeftMost(TreeParentNode node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}